package com.topcoder.srm512;

public class MysteriousRestaurant {
	public int maxDays(String[] prices, int budget) {
		int N = prices[0].length();
		int[][] sum = new int[7][N];
		int[] min = new int[7];
		
		int i;
		for (i=0; i<prices.length; i++) {
			int day = i%7;
			min[day] = Integer.MAX_VALUE;
			for (int j=0; j<N; j++) {
				sum[day][j] += getPrice(prices[i].charAt(j));
				min[day] = Math.min(min[day], sum[day][j]);
			}
			
			int s = 0;
			for (int j=0; j<7; j++) s += min[j];
			if (s > budget) break;
		}
		
		return i;
	}
	
	private int getPrice(char c) {
		if (c >= '0' && c <= '9') return c - '0';
		if (c >= 'A' && c <= 'Z') return 10 + c - 'A';
		return 36 + c - 'a';
	}
	
	public int maxDays2(String[] prices, int budget) {
        int right = prices.length + 1;
        int left = 0;
        while (right - left > 1) {
            int middle = (left + right) / 2;
            int cost = 0;
            for (int i = 0; i < 7; ++i) {
                int[] total = new int[prices[0].length()];
                for (int j = i; j < middle; j += 7) {
                    for (int k = 0; k < total.length; ++k) {
                        char ch = prices[j].charAt(k);
                        total[k] += getPrice(ch);
                    }
                }
                int min = Integer.MAX_VALUE;
                for (int x : total) min = Math.min(min, x);
                cost += min;
            }
            if (cost <= budget)
                left = middle;
            else
                right = middle;
        }
    return left;
  }
}
